package com.zp.self.module.level_4_算法练习.算法.排序;

import org.junit.Assert;
import org.junit.Test;

import java.util.Arrays;
import java.util.Stack;

/**
 * @author By ZengPeng
 */

public class V_归并排序_O_nXlogn {
    @Test
    public void main() {
        int[] orderly = {1, 3, 3, 4, 4, 4, 5, 5, 5, 6, 6, 6, 7, 23, 23, 65, 76, 213, 231, 322, 432, 3132, 4324, 12321};
        int[] arr = {7, 1, 5, 3, 6, 4,3,4,5,65,6,322,23,231,23,213,5,4,6,76,432,4324,12321,3132};
        for (int i = 0; i < 100; i++) {//打乱100次，验证排序的正确性
            猴子排序_量子级别.shuffle(arr);
            mergeSort(arr);
            Assert.assertEquals( Arrays.toString(orderly),Arrays.toString(arr));
        }
        mergeSort(arr);
        System.out.println(Arrays.toString(arr));
    }

    /**
     题目：归并排序：时间：O(n*logn) 、空间：O(n)、顺序稳定

     分析：
            原理：【分治法】不断2分数组，将小块排序，然后在合并小块
            实现： 1.递归实现
                   2.非递归 -- 栈实现

     **/

    public void mergeSort(int[] nums) {
//        recursionSort(nums,0,nums.length-1,new int[nums.length]);//排序[mid,length-1]
        //stackMergeSort(nums);
        iterationSort(nums);
    }

    /**
     * Description: 非递归归并排序
     *      1.外循环控制区间大小，内循环合并区间
     */
    private void iterationSort(int[] nums) {
        int[] temp = new int[nums.length];
        for (int i = 1; i < temp.length; i+=i) {
            for (int j = 0; j < temp.length; j+=i) {
                int left =j, right = Math.min(j+i, temp.length - 1),mid=left+(right-left)/2;
                int newL=j,newR=mid+1,tempIndex = j;
                while (newL<=mid && newR<=right){
                    //合并[left,mid]  、[mid+1,right]  == 由于两个数列都已经有序，我们只需从两个数列的低位轮番拿出各自最小的数来PK就就行了
                    if(nums[newL]<nums[newR]){
                        temp[tempIndex++] = nums[newL++];
                    }else {
                        temp[tempIndex++] = nums[newR++];
                    }
                }
                while (newL<=mid)//左边存在未编入temp的元素，则编入temp
                    temp[tempIndex++] = nums[newL++];
                while (newR<=right)//右边存在未编入temp的元素，则编入temp
                    temp[tempIndex++] = nums[newR++];
                while (left<=right)//将排好序的那一部分赋值给numbs
                    nums[left] = temp[left++];
            }
        }
    }

    //递归3步曲：单步操作、终止条件、返回值
    private void recursionSort(int[] nums, int left, int right, int[] temp) {//排序这个区间的数据
        if(left==right)return;
        int mid = left+(right-left)/2;
        recursionSort(nums,left,mid,temp);//排序[left,mid]
        recursionSort(nums,mid+1,right,temp);//排序[mid+1,right]
        //有序段--左边的起点，右边的起点，临时数组的开始下标
        int newL=left,newR=mid+1,tempIndex = left;
        while (newL<=mid && newR<=right){ //合并[left,mid]  、[mid+1,right]  == 由于两个数列都已经有序，我们只需从两个数列的低位轮番拿出各自最小的数来PK就就行了
            if(nums[newL]<nums[newR]){
                temp[tempIndex++] = nums[newL++];
            }else {
                temp[tempIndex++] = nums[newR++];
            }
        }
        while (newL<=mid)//左边存在未编入temp的元素，则编入temp
            temp[tempIndex++] = nums[newL++];
        while (newR<=right)//右边存在未编入temp的元素，则编入temp
            temp[tempIndex++] = nums[newR++];
        while (left<=right)//将排好序的那一部分赋值给numbs
            nums[left] = temp[left++];
    }



    /**
     * Description: 归并排序非递归 -- 栈实现 【感觉效率还没右递归高，多创建了一个stack的内存】
     * stack：存储当前区间
     * stackAll：存储所有要比较的区间
     * 大区间弹出，得到两个小区间，全部放入stackAll存储起来：
     */
    private void stackMergeSort(int[] nums) {
        //eg:  {6,4,5,1,7,3,2}
        //下标: 0 1 2 3 4 5 6
        //记录即将要合并的区间？stackAll中将存储： [0,6]、[0,3]、[4,6]、[4,5]、[0,1]、[2,3]
        //然后弹奏stackAll：将下标[2,3]、[0,1]、[4,5]排序为有序.
        // 再弹栈到[4,6] 时：[4,5] 和 [6] 已经左右有序了，根据mid==5 ,再排序[4,6]区间即可
        Stack<int[]> stack = new Stack<>();//用于记录
        Stack<int[]> stackAll = new Stack<>();
        stack.add(new int[]{0,nums.length-1});
        stackAll.add(new int[]{0,nums.length-1});
        while (!stack.isEmpty()){
            int[] arr = stack.pop();
            int mid = arr[0]+(arr[1]-arr[0])/2;
            if(arr[0]==arr[1]) continue;
            stack.add(new int[]{arr[0],mid});
            stack.add(new int[]{mid+1,arr[1]});
            stackAll.add(new int[]{arr[0],mid});//将每个小区间存储到 栈中，当先弹出空间进行排序时，他之前的小空间就已经被排序好了，
            stackAll.add(new int[]{mid+1,arr[1]});// 只需要合并这个区间内的有序集合，两个有序集合的分界点是mid
        }
        //开始合并
        int[] temp = new int[nums.length];
        while (!stackAll.isEmpty()){
            int[] section = stackAll.pop();
            int left =section[0],right = section[1],mid =left+(right-left)/2 ;//得到此区间两个有序集合的中间分割点mid
            //有序段--左边的起点，右边的起点，临时数组的开始下标
            int newL=left,newR=mid+1,tempIndex = left;
            while (newL<=mid && newR<=right){ //合并[left,mid]  、[mid+1,right]  == 由于两个数列都已经有序，我们只需从两个数列的低位轮番拿出各自最小的数来PK就就行了
                if(nums[newL]<nums[newR]){
                    temp[tempIndex++] = nums[newL++];
                }else {
                    temp[tempIndex++] = nums[newR++];
                }
            }
            while (newL<=mid)//左边存在未编入temp的元素，则编入temp
                temp[tempIndex++] = nums[newL++];
            while (newR<=right)//右边存在未编入temp的元素，则编入temp
                temp[tempIndex++] = nums[newR++];
            while (left<=right)//将排好序的那一部分赋值给numbs
                nums[left] = temp[left++];
        }
    }
}


